Digital signatures are often employed to ensure the authenticity of transmitted information. A message generator generates a digital signature, s, using a public-key method, such as RSA public key cryptography techniques or the Rabin signature scheme. The message generator sends a message, m, and the signature, s, to a receiver. A Rabin signature, s, typically has a length on the order of 1024 bits. Thus, the Rabin signature scheme adds a significant overhead to a transmitted message. A number of techniques have thus been proposed or suggested for compressing Rabin signatures. Generally, the compression techniques aim to send only a portion of the Rabin signature, such that the transmitted portion is sufficient to reconstruct the full signature.
For example, Coron and Naccache have shown that a Rabin signature can be reconstructed if, for example, more than half of the most significant bits of s are known. See, International Published Patent Application No. WO 03/021864 A2, “Method and Apparatus of Reducing the Size of an RSA or Rabin Signature,” to Jean Sebastien Coron and David Nacacche, Published Mar. 13, 2003. Generally, Coron and Naccache use Coppersmith's LLL-based root finding method, as described in Don Coppersmith, “Finding a Small Root of a Univariate Modular Equation,” Advances in Cryptology, EUROCRYPT '96, Vol. 1070 of Lecture Notes in Computer Science, 155-165 (1996; Springer Verlag). The Coppersmith LLL-based root finding method leads to a slow decompression when the fraction of known bits is close to fifty percent (50%).
It has been suggested that a fast decompression method can be found when at least ⅔ of the bits are given. As used herein, a “fast compression method” means significantly faster than generating a signature (e.g., faster than 1 millisecond on a 1 MHz computer) and a “slow decompression method” means significantly slower than generating a signature (e.g., longer than 1 second on a 1 MHz computer). A need therefore exists for a fast compression method that can compress a Rabin signature by fifty percent.